package com.jeff.practice;

/**
 <h1 style="color:red">求股票买卖中的最大利润</h1>
 * 给定一个数组arr，其中arr[i]表示第i天的股票价格，请设计一个算法，求出最大利润。
 * 假设每天只能买入或卖出一支股票，且一次只能买入或卖出一支股票 整个过程只能买卖一次。
 * 只能先买再卖，不能同时买卖。
 * 算法的基本思路是：
 * 1. 先求出数组中的最大值和最小值，并记录其索引
 * 2. 如果最大值索引大于最小值索引，则最大利润为最大值减去最小值
 * 3. 如果最大值索引小于最小值索引，则将原始数组以最小值索引为分界点，分成两部分，分别求最大利润
 * 4. 递归求解两部分的最大利润，取其中的最大值
 * 5. 返回最大利润
 * @author yaojianfeng
 */
public class StockMaxValue1 {
    public static void main(String[] args) {
        int[] arr = {3, 4, 1, 6, 8, 2, 9, 5, 7};
        int[] arr2 = {7, 1, 5, 3, 6, 4};
        int test = test(arr);
        System.out.println(test);

    }

    public static int test(int[] arr) {
        if (arr.length <= 1) {
            return 0;
        }
        //求数组中的最大值和最小值
        int max = arr[0];
        int maxIndex = 0;
        int min = arr[0];
        int minIndex = 0;
        int maxValue = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
                maxIndex = i;
            }
            if (arr[i] < min) {
                min = arr[i];
                minIndex = i;
            }
        }
        if (maxIndex > minIndex) {
            maxValue = max - min;
        } else {
            //将原始数组以最小值索引为分界点,分成两部分
            int[] left = new int[minIndex];
            int[] right = new int[arr.length - minIndex];
            System.arraycopy(arr, 0, left, 0, minIndex);
            System.arraycopy(arr, minIndex, right, 0, arr.length - minIndex);
            maxValue = Math.max(test(left), test(right));
        }
        return maxValue;
    }
}
